package 回文串;

public class test4 {
    public int minCut(String s) {
        // dp[i]: 表示s[0,i]之间最少的分割次数
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        for (int i = n-1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if(s.charAt(i)==s.charAt(j)){
                    dp[i][j] = i+1<j?dp[i+1][j-1]:true;
                }else dp[i][j] = false;
            }
        }

        int[] result = new int[n];
        for (int i = 0; i < n; i++) result[i] = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            if(dp[0][i]) result[i] = 0; //判定从0到i
            else {
                for (int j = 1; j <= i; j++) {
                    if(dp[j][i]) result[i] = Math.min(result[i],result[j-1]+1);
                }
            }
        }
        return result[n-1];
    }
}
